package main

import (
	"fmt"
	"math/rand"
	"time"
)

func bubbleSort(arr []int) []int {
	length := len(arr)
	for i := 0; i < length; i++ {
		for j := 0; j < length-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	return arr
}

func bucketSort(arr []int) []int {
	length := len(arr)
	if length <= 10 {
		return bubbleSort(arr)
	}
	minValue := arr[0]
	maxValue := arr[0]

	for i := 0; i < length; i++ {
		if minValue > arr[i] {
			minValue = arr[i]
		}
		if maxValue < arr[i] {
			maxValue = arr[i]
		}
	}

	buckets := make([][]int, (maxValue-minValue)/length+1)
	for i := 0; i < length; i++ {
		bucketIndex := (arr[i] - minValue) / length
		buckets[bucketIndex] = append(buckets[bucketIndex], arr[i])
	}

	key := 0
	for _, bucket := range buckets {
		if len(bucket) <= 0 {
			continue
		}
		bubbleSort(bucket)
		for _, value := range bucket {
			arr[key] = value
			key++
		}
	}
	return arr
}

func main() {
	arr := make([]int, 100)
	rand.Seed(time.Now().UnixNano())

	length := len(arr)
	for i := 0; i < length; i++ {
		arr[i] = rand.Intn(1000)
	}
	fmt.Println(arr)
	fmt.Println(bucketSort(arr))
}
